// chain with bin sort included

#ifndef chain_
#define chain_

#include <iostream>
#include <sstream>
#include <string>
#include "linearList.h"
#include "chainNode.h"
#include "myExceptions.h"
#include "studentRecord2.h"

using namespace std;

template <class T>
class chain : public linearList<T>
{
public:
    // constructor, copy constructor and destructor
    chain(int initialCapacity = 10);
    chain(const chain<T> &);
    ~chain();

    // ADT methods
    bool empty() const { return listSize == 0; }
    int size() const { return listSize; }
    T &get(int theIndex) const;
    int indexOf(const T &theElement) const;
    void erase(int theIndex);
    void insert(int theIndex, const T &theElement);
    void output(ostream &out) const;

    // additional methods
    void binSort(int range);
    void binSort(int range, int (*value)(T &x));

protected:
    void checkIndex(int theIndex) const;
    // throw illegalIndex if theIndex invalid
    chainNode<T> *firstNode; // pointer to first node in chain
    int listSize;            // number of elements in list
};

template <class T>
chain<T>::chain(int initialCapacity)
{ // Constructor.
    if (initialCapacity < 1)
    {
        ostringstream s;
        s << "Initial capacity = " << initialCapacity << " Must be > 0";
        throw illegalParameterValue(s.str());
    }
    firstNode = NULL;
    listSize = 0;
}

template <class T>
chain<T>::chain(const chain<T> &theList)
{ // Copy constructor.
    listSize = theList.listSize;

    if (listSize == 0)
    { // theList is empty
        firstNode = NULL;
        return;
    }

    // non-empty list
    chainNode<T> *sourceNode = theList.firstNode;
    // node in theList to copy from
    firstNode = new chainNode<T>(sourceNode->element);
    // copy first element of theList
    sourceNode = sourceNode->next;
    chainNode<T> *targetNode = firstNode;
    // current last node in *this
    while (sourceNode != NULL)
    { // copy remaining elements
        targetNode->next = new chainNode<T>(sourceNode->element);
        targetNode = targetNode->next;
        sourceNode = sourceNode->next;
    }
    targetNode->next = NULL; // end the chain
}

template <class T>
chain<T>::~chain()
{ // Chain destructor. Delete all nodes in chain.
    chainNode<T> *nextNode;
    while (firstNode != NULL)
    { // delete firstNode
        nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}

template <class T>
void chain<T>::checkIndex(int theIndex) const
{ // Verify that theIndex is between 0 and listSize - 1.
    if (theIndex < 0 || theIndex >= listSize)
    {
        ostringstream s;
        s << "index = " << theIndex << " size = " << listSize;
        throw illegalIndex(s.str());
    }
}

template <class T>
T &chain<T>::get(int theIndex) const
{   // Return element whose index is theIndex.
    // Throw illegalIndex exception if no such element.
    checkIndex(theIndex);

    // move to desired node
    chainNode<T> *currentNode = firstNode;
    for (int i = 0; i < theIndex; i++)
        currentNode = currentNode->next;

    return currentNode->element;
}

template <class T>
int chain<T>::indexOf(const T &theElement) const
{   // Return index of first occurrence of theElement.
    // Return -1 if theElement not in list.

    // search the chain for theElement
    chainNode<T> *currentNode = firstNode;
    int index = 0; // index of currentNode
    while (currentNode != NULL &&
           currentNode->element != theElement)
    {
        // move to next node
        currentNode = currentNode->next;
        index++;
    }

    // make sure we found matching element
    if (currentNode == NULL)
        return -1;
    else
        return index;
}

template <class T>
void chain<T>::erase(int theIndex)
{   // Delete the element whose index is theIndex.
    // Throw illegalIndex exception if no such element.
    checkIndex(theIndex);

    // valid index, locate node with element to delete
    chainNode<T> *deleteNode;
    if (theIndex == 0)
    { // remove first node from chain
        deleteNode = firstNode;
        firstNode = firstNode->next;
    }
    else
    { // use p to get to predecessor of desired node
        chainNode<T> *p = firstNode;
        for (int i = 0; i < theIndex - 1; i++)
            p = p->next;

        deleteNode = p->next;
        p->next = p->next->next; // remove deleteNode from chain
    }
    listSize--;
    delete deleteNode;
}

template <class T>
void chain<T>::insert(int theIndex, const T &theElement)
{ // Insert theElement so that its index is theIndex.
    if (theIndex < 0 || theIndex > listSize)
    { // invalid index
        ostringstream s;
        s << "index = " << theIndex << " size = " << listSize;
        throw illegalIndex(s.str());
    }

    if (theIndex == 0)
        // insert at front
        firstNode = new chainNode<T>(theElement, firstNode);
    else
    { // find predecessor of new element
        chainNode<T> *p = firstNode;
        for (int i = 0; i < theIndex - 1; i++)
            p = p->next;

        // insert after p
        p->next = new chainNode<T>(theElement, p->next);
    }
    listSize++;
}

template <class T>
void chain<T>::output(ostream &out) const
{ // Put the list into the stream out.
    for (chainNode<T> *currentNode = firstNode;
         currentNode != NULL;
         currentNode = currentNode->next)
        out << currentNode->element << "  ";
}

// overload <<
template <class T>
ostream &operator<<(ostream &out, const chain<T> &x)
{
    x.output(out);
    return out;
}

template <class T>
void chain<T>::binSort(int range)
{ // Sort the nodes in the chain.
    // create and initialize the bins
    chainNode<T> **bottom, **top;
    bottom = new chainNode<T> *[range + 1];
    top = new chainNode<T> *[range + 1];
    for (int b = 0; b <= range; b++)
        bottom[b] = NULL;

    // distribute to bins
    for (; firstNode != NULL; firstNode = firstNode->next)
    {                                    // add firstNode to proper bin
        int theBin = firstNode->element; // type conversion to int
        if (bottom[theBin] == NULL)      // bin is empty
            bottom[theBin] = top[theBin] = firstNode;
        else
        { // bin not empty
            top[theBin]->next = firstNode;
            top[theBin] = firstNode;
        }
    }

    // collect from bins into sorted chain
    chainNode<T> *y = NULL;
    for (int theBin = 0; theBin <= range; theBin++)
        if (bottom[theBin] != NULL)
        {                  // bin not empty
            if (y == NULL) // first nonempty bin
                firstNode = bottom[theBin];
            else // not first nonempty bin
                y->next = bottom[theBin];
            y = top[theBin];
        }
    if (y != NULL)
        y->next = NULL;

    delete[] bottom;
    delete[] top;
}

template <class T>
void chain<T>::binSort(int range, int (*value)(T &x))
{ // Sort the nodes in the chain. The sort key is value(theElement).
    // create and initialize the bins
    chainNode<T> **bottom, **top;
    bottom = new chainNode<T> *[range + 1];
    top = new chainNode<T> *[range + 1];
    for (int b = 0; b <= range; b++)
        bottom[b] = NULL;

    // distribute to bins
    for (; firstNode != NULL; firstNode = firstNode->next)
    { // add firstNode to proper bin
        int theBin = value(firstNode->element);
        // type conversion to int
        if (bottom[theBin] == NULL) // bin is empty
            bottom[theBin] = top[theBin] = firstNode;
        else
        { // bin not empty
            top[theBin]->next = firstNode;
            top[theBin] = firstNode;
        }
    }

    // collect from bins into sorted chain
    chainNode<T> *y = NULL;
    for (int theBin = 0; theBin <= range; theBin++)
        if (bottom[theBin] != NULL)
        {                  // bin not empty
            if (y == NULL) // first nonempty bin
                firstNode = bottom[theBin];
            else // not first nonempty bin
                y->next = bottom[theBin];
            y = top[theBin];
        }
    if (y != NULL)
        y->next = NULL;

    delete[] bottom;
    delete[] top;
}
#endif
